先來看一下題目

Given an array of positive integers (representing coins), find the smallest value that cannot be constructed from those integers.

這題算是網路蠻多人分享的找零錢變形題，實作起來很簡單，其實難度也不高，但是如果沒有看過遇過，突然被考到還真的會想不到好的作法！

我們一起來推推看吧！
簡單來說這題題目就是在問:
假設給你一堆金幣(都是大於０的數) ，找出這些金幣不能組出來的最小值
當然我們不可以重複用同樣的金幣，不然如果給你1塊就全部都可以湊出來了!

一開始看到題目很直覺的想法就是:
從1開始確認，1有沒有辦法被這些數字組成, 2, 3, ... → 暴力
我相信大家一開始都會覺得很簡單啊解完了！但這覺對不是最好的方式！

『再想想有沒有更好的方式？』
（很常在解題目毫無頭緒的時候，看到有Array就可以想到排序）

如果先把array排序會有幫助嗎？因為是找是找最小值，應該有幫助吧？

假設 input : [6, 4, 5, 1, 1, 8, 9]
sortedInput -> [1, 1, 4, 5, 6, 8, 9]

我們從1開始，先把一開始可以湊到的最多金額數設為 0 （currentMax = 0）
取出sortedInput[0]= 1 -> 把 currentMax ０加上１-> currentMax = １
也就是我們可以湊到的最多為1

接著我們又可以拿到 sortedInput[1]= 1
所以 １＋１＝２ (currentMax = 2)
我們現在可以湊到的數為 {1, 2}

接著我們拿到 4
4 - 2 = 2 > 1
我們現在最大可以湊到的數是 1 + 1 + 4 = 6
我們現在可以湊到的數為 {1, 2, 4, 5, 6}

那3要怎麼湊呢？ (沒錯答案就是3)
在這裡我們可以發現，每次我們在湊錢的時候，
如果拿到下一個數，和前面加起來目前湊到最大的數相差大於1，那個數就是答案。

欸等等，為什麼？ <- (我一開始看到別人這樣做的時候的反應！)

我們來想想！
我們每次在檢查當下的數時都存了當下可以組成的最大的數，
而我們知道下一個想要組合而成的數都是當下組成的最大的數+1(也就是目前走到input array地方的所有數和＋１)
那個如果下一個數不是剛好是組成的最大的數+1,
我們不就沒有辦法拿到其他的數來得到目前組成的最大的數+1嗎?
是不是瞬間有頭緒了！！

Time Complexity: O(nlogn) -> 時間主要花在排序，只用檢查一次陣列
Space Complexity: O(1) (or O(n) 如果不能使用in place sort)

最後來看程式碼吧！

function nonConstructibleChange(coins) {
  coins.sort((a,b) => a-b);
	let currentMax = 0;
	for(const coin of coins){
		if (coin > currentMax + 1) return currentMax + 1;
		currentMax += coin;
	}
  return currentMax + 1;
}

Reference: Elements of Programming Interviews in python, page 189

明日題目預告:
入門不可以錯過的題目 Two Sum